/*
 * @lc app=leetcode.cn id=18 lang=csharp
 *
 * [18] 四数之和
 */

// @lc code=start
public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        var result = new List<IList<int>>();
        Array.Sort(nums);

        int n = nums.Length;
        for (int i = 0; i < n - 3; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            // 剪枝：最小和大于 target，后续 i 只会更大，直接结束
            long minI = (long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];
            if (minI > target)
            {
                break;
            }
            // 剪枝：最大和小于 target，当前 i 不可能达成，跳过
            long maxI = (long)nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3];
            if (maxI < target)
            {
                continue;
            }

            for (int j = i + 1; j < n - 2; ++j)
            {
                if (j > i + 1 && nums[j] == nums[j - 1])
                {
                    continue;
                }

                // 二级剪枝
                long minJ = (long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2];
                if (minJ > target)
                {
                    break;
                }
                long maxJ = (long)nums[i] + nums[j] + nums[n - 1] + nums[n - 2];
                if (maxJ < target)
                {
                    continue;
                }

                int left = j + 1;
                int right = n - 1;
                while (left < right)
                {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target)
                    {
                        result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });

                        int leftVal = nums[left];
                        int rightVal = nums[right];
                        while (left < right && nums[left] == leftVal) ++left;
                        while (left < right && nums[right] == rightVal) --right;
                    }
                    else if (sum < target)
                    {
                        ++left;
                    }
                    else
                    {
                        --right;
                    }
                }
            }
        }
        return result;
    }
}
// @lc code=end

